package algorithms.leecode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Au94 {

      static class TreeNode {
         int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
              this.left = left;
              this.right = right;
         }
      }
    static class Solution {
         static Stack<TreeNode> stack = new Stack<>();
        static List<Integer> res = new ArrayList<>();

        public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            TreeNode second = new TreeNode(2);
            TreeNode third = new TreeNode(3);
            root.right = second;
            second.left = third;
            inorderTraversal(root);

        }
        public static List<Integer> inorderTraversal(TreeNode root) {
          push(root);
          return res;

        }

        public static void pop() {
            while (!stack.isEmpty()) {
                if (stack.peek().right != null) {
                    res.add(stack.peek().val);
                    push(stack.pop().right);
                } else {
                    res.add(stack.pop().val);
                }
            }
        }
        public static void push(TreeNode root){
            TreeNode curr = root;
            while (curr.left != null) {
                stack.push(curr);
                curr = curr.left;
            }
            stack.push(curr);
            pop();

        }
    }
}
